1. Field of the Invention
The present invention relates to a data compression method and system. More in particular, it relates to a method for designing an optimal scalar quantizer to be used in communications or storage systems.
In a communication system, the information to be sent along a channel is usually encoded by means of a source coder, which compresses the data to be sent. The source coder employs a source code that can either be lossless or lossy. A lossless source code is completely reversible, while a lossy source code creates a distortion of the signal to be transmitted. Any lossy source code can be described as a quantizer followed by a lossless compression algorithm. The quantizer performs an approximation step and the lossless compression algorithm performs a lossless compression step.
Quantizers that operate on blocks of source output are called vector quantizers. Quantizers that quantize each output separately are called scalar quantizers. In scalar quantization, each single-source output is quantized to one of some number of levels, and these levels are encoded into a binary sequence. See, for example, xe2x80x9cCommunication Systems Engineering,xe2x80x9d John G. Proakis and Masoud Salehi, Prentice-Hall Inc., 1994, p. 246.
For example, the initial source alphabet can be a list of 256 brightness levels numbered from 0 to 255 in a gray scale image. Each symbol can have a certain relative frequency, or probability, so that a list of symbol/probability pairs can be defined, forming a discrete probability function, also known as probability mass function or pmf. A scalar quantizer would approximate the initial source alphabet with a smaller set, for example, the set {10, 35, 49, 102} by mapping each number between 0 and 255 to either 10, 35, 49 or 102. A new probability function would arise, given by the relative frequencies of 10, 35, 49 and 102 in the approximation. The xe2x80x9cdistortion measurexe2x80x9d quantities indicate how badly the data is distorted by the chosen mapping.
The output of the quantizer is assumed to go to a lossless compression algorithm, which introduces no further approximations, but produces a more compact representation of the data by taking advantage of its redundancy. The quantizer mapping is chosen with the aim of both keeping the distortion low and allowing a compact representation. The xe2x80x9cratexe2x80x9d describes how compact the representation is, with lower rate indicating a shorter data representation. The shorter data descriptions require less memory to store and less time to transmit. Generally, coarser approximations yield higher distortion and lower rate.
There are two important rate measures: in xe2x80x9cfixed ratexe2x80x9d scenarios, the number of symbols for the approximation is fixed, and each approximation has the same description length. Therefore, the rate does not enter into consideration, and all that remains in quantizer design is the choice of approximation symbols that yield the least distortion, i.e. the least approximation error. In xe2x80x9cvariable ratexe2x80x9d scenarios, the number of approximating symbols is not fixed beforehand and each approximation can have a different description length.
In some systems, an optional initial transform step is provided, where an initial reversible transformation is performed as preprocessing. The code then quantizes the transformed data. The reconstruction process replaces each description by its corresponding reconstruction and then reverses the transformation.
When only one approximation of the original data is given, the quantizer is called a single-description quantizer. However, there is a need to design quantizers not limited to single-description scenarios, but also capable of handling other coding scenarios, like multiple description and multiple resolution coding.
Multiple description refers to the simultaneous production of two or more approximations of the original data. Some approximations are given independent descriptions, while others are reached by combining two or more of the independent descriptions. Reference can be made, for example, to a communications system where more than one path is available, like the case, for example, of one transmitter and multiple receiving antennas. In such case, the different descriptions will travel independently, and some of them may not be received at all.
Multiple description (MD) can be general or restricted. In general-MD, all scenarios are a-priori possible. In restricted-MD, some combinations are known to be impossible. Therefore, in restricted-MD, the sender can make certain assumptions that reduce the number of scenarios to be considered and simplify the code. A special case of restricted-MD is called multi-resolution. In multi-resolution, each description is received only if the previous ones have been received, so that description 3 cannot arrive without description 1 and description 2. A specialized version of the method according to the present invention runs much faster in the multi-resolution case.
Throughout the description of the present invention, reference will be made to the enclosed Annex A, which makes part of the present disclosure. Annex A also contains a reference to twenty prior art publications. The same notation [1] . . . [20] used for those references in Annex A will be used throughout the description.
2. Description of the Prior Art
Prior art approaches in globally optimal scalar quantizer design for fixed-rate, single-encoder, single-decoder codes for finite-alphabet sources are known. See, for example, references [1], [2], [3], and [4] of Annex A.
A quantizer design algorithm for variable-rate scalar quantization is also known from reference [2] of Annex A, but is very slow.
Additionally, algorithms are known which handle both fixed- and variable-rate, single or multiple descriptions, by iterative methods, where the initial step is that of providing an arbitrary solution and then obtaining a better solution after each iteration. However, these algorithms do not necessarily yield an optimal quantizer, and have no bound on the running time.
Therefore, there is a need for a method for designing an optimal quantizer for signal encoding/decoding which can be applied to the multiple environments described above. Such method must also have a polynomial complexity.
The present invention overcomes the above limitations and problems by providing a method which finds a quantizer in single-description and multiple-description scenarios with polynomial complexity. Under appropriate conditions, explained throughout the following description, the quantizer is the optimal quantizer. In particular, the quantizer according to the present invention is optimal when it provides the optimum rate/distortion tradeoff. An optimum rate/distortion combination is a combination which makes the rate no larger than some specified allowed value and reduces distortion as much as possible. In particular, the improvement in the quantizer distortion associated with a small increase in rate is matched to a desired target value. The target value is chosen so that the distortion is minimized.
According to a first aspect of the present invention, a signal encoding system having a coder for encoding signals is provided, the coder including a quantizer and a lossless coder, the quantizer producing a distortion on the signals to be encoded, wherein the quantizer is an optimal quantizer under a rate/distortion tradeoff, so that the distortion is minimized when the rate of the optimal quantizer is no larger than a specified value.
According to a second aspect of the present invention, a signal decoding system having a decoder for decoding signals is provided, the decoder including a lossless decoder and an inverse quantizer wherein the inverse quantizer is an optimal quantizer under a rate/distortion tradeoff, so that the distortion is minimized when the rate of the optimal quantizer is no larger than a specified value.
According to a third aspect of the present invention, a signal encoding method for use in a signal encoding system is provided, comprising the steps of: providing a source alphabet containing a set of source characters; approximating the set of source characters by designing a quantizer and applying the designed quantizer to the set of source characters, thus producing a distortion on the set of source characters; and applying a compression algorithm to the smaller set of characters, wherein the step of designing a quantizer comprises the steps of: defining a target function depending on the distortion on the set of source characters; and minimizing the target function.
According to a fourth aspect of the present invention, a client-server system comprising a server and a plurality of clients is provided, wherein when a client of the plurality of clients requests data to the server, the server provides the client with an approximation of the requested data, the approximation being based on a quantization process of the requested data, thus producing distortion on the requested data, the quantization process approximating the requested data to a smaller number of data and comprising a step of designing a quantizer by defining a target function and minimizing the target function.
The method according to the present invention can be applied to a variety of coding scenarios (single-description; general or restricted multiple description; and multi-resolution), under a variety of distortion measures (for example, mean-squared error; absolute error; other monotonic error measures) and under fixed- or variable-rate, in a bounded and reasonable amount of time (polynomial complexity).
According to a first step of the present invention, the quantizer design problem is transformed into a graph problem. In a further step, graph algorithms are used to solve the graph problem; and, in a third step, the graph solution is transformed into a quantizer, which represents the solution to the original problem.
More specifically, in the first step, a weighted directed acyclic graph (WDAG) is built, based on the parameters of the problem. A graph consists of a set of nodes, and a set of edges between nodes. The graph used in the preferred embodiment of the present invention is directed because each edge has an arrow (orientation) on it; weighted because each edge has a weight; and acyclic because there are no circuits.
In the second step, the method according to the present invention uses either the xe2x80x9csingle-source WDAG shortest path algorithmxe2x80x9d or the xe2x80x9call-pairs WDAG shortest path algorithmxe2x80x9d to obtain a path between two special nodes of the graph such that the sum of the weights of the edges that make up the path is minimal. Both kinds of the xe2x80x9cshortest path algorithmxe2x80x9d employ a topological sort algorithm, known as such in the prior art. Finally, the path is xe2x80x9cdecodedxe2x80x9d to obtain a xe2x80x9cpartitionxe2x80x9d of the source alphabet. Such partition defines the quantizer.
The quantizer can then be combined with any lossless compression algorithm and optionally with a reversible transformation to yield a lossy compression scheme.
A main advantage of the method and system according to the present invention is that the time complexity of the algorithm it employs is polynomial. The time complexity of an algorithm is the amount of time (or number of steps) it takes to complete, as a function of the size of the input. The input size in the present invention is the number of symbol/probability pairs. The method according to the present invention runs in polynomial time in all embodiments. In the enclosed Annex A the degree of the polynomial is computed for each specific case. It should be noted that the polynomial time complexity of the method according to the present invention is a relevant result, because a brute-force method (examining all quantizers and choosing the best one) will take exponential time, because the number of possible quantizers for N symbols is 2N.
A further advantage of the method is that it yields a code that is guaranteed to be the best of all possible codes with xe2x80x9ccontiguous codecells.xe2x80x9d For fixed- and variable-rate single description, no other algorithm can yield better codes.
Since the method according to the present invention makes use of a trade-off parameter between rate and distortion, such method is particularly well suited for xe2x80x9csmart serverxe2x80x9d applications where a client requests the data and the server delivers a suitable approximation, based on the available bandwidth, so that more rate and less distortion for large bandwidth, and less rate and more distortion for small bandwidth, are provided.
Examples of applications of the method according to the present invention could include a digital camera, a hand-held scanner, a medical image database or any other image server, where the server or device can store images in an efficient proprietary format internally to maximize usage of its limited memory, and produce a compressed file for download when required.
Additionally, a multiple description quantizer design is useful for xe2x80x9cdiversity codingxe2x80x9d in wireless communications where more than one channel may be available and in packet networks like the Internet.
The quantizer designer method according to the present invention can be used as part of a lossy compression scheme like compression algorithms for images, video and audio. Additionally, the method according to the present invention can work with any kind of discrete-time signal, one-dimensional or multi-dimensional, like for example a sound signal, an image signal, or a time-series signal.